#include <iostream>
using namespace std;

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int x) 
    {
        if(data.empty())
			return 0;
		int idxBg = -1,idxEd = -1;
		idxBg = findFirstK(data,x);
		idxEd = findLastK(data,x);
		if(idxBg != -1 && idxEd != -1)
		{
			return idxEd - idxBg +1;
		}
		return 0;
    }

    int findFirstK(vector<int> data,int x)
	{
		int begin = 0 , end = data.size() -1 ,mid = (begin+end)/2;
		while(begin <= end)
		{
			if(data[mid]>x)
				end = mid -1;
			else if(data[mid] < x)
				begin = mid +1;
			else 
			{
				if(mid == 0 || data[mid-1] < x)
					return mid;
				else
					end = mid - 1;
			}
			mid = (begin+end)/2;
		//	cout<<" mid : "<<mid<<endl;
		}
		return -1;
	}

	int findLastK(vector<int> data,int x)
	{
		int begin = 0 , end = data.size() -1 ,mid = (begin+end)/2;
		while(begin <= end)
		{
			if(data[mid]>x)
				end = mid -1;
			else if(data[mid] < x)
				begin = mid +1;
			else 
			{
				if(mid == data.size()-1 || data[mid+1] > x)
					return mid;
				else
					begin = mid + 1;
			}
			mid = (begin+end)/2;
		//	cout<<" mid : "<<mid<<endl;
		}
		return -1;
	}

};


int main()
{
	int data[] = {1,2,3,3,3,3,4,5};
	int data1[] = {1,3,5,7,9};
	int data2[] = {5};
	cout<<binarySearchNumberOfK(data,3,8)<<endl;
	cout<<binarySearchNumberOfK(data1,6,5)<<endl;
	cout<<binarySearchNumberOfK(data1,5,5)<<endl;
	cout<<binarySearchNumberOfK(data1,1,5)<<endl;
	cout<<binarySearchNumberOfK(data1,9,5)<<endl;
	cout<<binarySearchNumberOfK(data2,5,1)<<endl;

	system("pause");
	return 0;
}
